Strong duality and sensitivity analysis in semi-infinite linear programming

摘要

Finite-dimensional linear programs satisfy strong duality (SD) and have the"dual pricing" (DP) property. The (DP) property ensures that, given asufficiently small perturbation of the right-hand-side vector, there exists adual solution that correctly "prices" the perturbation by computing the exactchange in the optimal objective function value. These properties may fail insemi-infinite linear programming where the constraint vector space is infinitedimensional. Unlike the finite-dimensional case, in semi-infinite linearprograms the constraint vector space is a modeling choice. We show that, for asufficiently restricted vector space, both (SD) and (DP) always hold, at thecost of restricting the perturbations to that space. The main goal of the paperis to extend this restricted space to the largest possible constraint spacewhere (SD) and (DP) hold. Once (SD) or (DP) fail for a given constraint space,then these conditions fail for all larger constraint spaces. We give sufficientconditions for when (SD) and (DP) hold in an extended constraint space. Ourresults require the use of linear functionals that are singular or purelyfinitely additive and thus not representable as finite support vectors. The keyto understanding these linear functionals is the extension of theFourier-Motzkin elimination procedure to semi-infinite linear programs.